package com.learn.acm.bytedance;

import com.google.gson.Gson;
import org.junit.jupiter.api.Test;

import java.nio.ByteBuffer;
import java.util.Arrays;
import java.util.Random;

/**
 * @author zhongshitao
 * @date 2020/9/24 10:38 上午
 */
public class QuickSort {




    public void testNIO() {
        ByteBuffer buf = ByteBuffer.allocate(1024);
    }


    @Test
    public void testQSort() {
        int[] nums = new int[10];
        for (int i = 0;i<nums.length;i++) {
            nums[i] = new Random().nextInt(100);
        }
        System.out.println(new Gson().toJson(nums));
        quickSort(nums);
        System.out.println(new Gson().toJson(nums));

    }

    public void quickSort(int[] nums) {
        nums = quickSort(nums, 0, nums.length-1);
    }


    private int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }

    private int partition(int[] arr, int left, int right) {
        // 设定基准值（pivot）
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        System.out.println(new Gson().toJson(arr) + "------" + pivot + "----" + index);
        swap(arr, pivot, index - 1);
        return index - 1;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    private void swap1(int[] arr, int left, int right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

    private void qSort1(int arr[], int left, int right) {
        if(left < right) {
            int partation = partition1(arr,left,right);
            qSort1(arr,left,partation -1);
            qSort1(arr, partation+1, right);
        }
    }

    private int partition1(int[] arr, int left, int right) {
        int pivot = left;
        int index = left + 1;
        for (int i = left;i<right;i++) {
            if (arr[pivot] > arr[index]) {
                swap1(arr, pivot, index);
            }
        }
        return index + 1;
    }

































}
